/*
    leetcode 204
    统计所有小于非负整数n的质数的数量

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

输入：n = 0
输出：0

输入：n = 1
输出：0

*/
/*
我 们 反 过 来 想 ， 任 何 一 个 质 数 比 如 a ， 他 的 n （ n>=2 ） 倍 一 定 不 是 质 数 ， 也 就 是
a*2，a*3……都不在是质数。我们可以申请一个长度为length的数组用来存储对
应的数是不是质数。然后在用一个变量count来统计质数的个数，如果是合数就不
需要统计，如果是质数，count就加1，然后再把质数的2倍，3倍……都标记为非
质数，
*/
#include<bits/stdc++.h>
using namespace std; 
class Solution {
public:
    int countPrimes(int n) {
        //用来标记，false表示为质数，true为合数
		vector<bool> composite(n,false);
		int count=0;//统计质数的个数
		for(int i=2;i<n;i++){
            //如果是合数，就不需要统计
			if(composite[i])
				continue;
            //到这一步说明是质数，直接让它的2倍，3倍...标记为合数
			count++;
			for(int j=i;j<n;j+=i)
				composite[j]=true;
		}
		return count;
    }
};